package 回溯;

import java.util.ArrayDeque;
import java.util.Deque;

//https://leetcode.cn/problems/number-of-islands/
public class 岛屿数量 {
    int[] x = new int[]{-1 , 0 , 0 , 1};
    int[] y = new int[]{0 , -1 , 1 , 0};
    int n = 0;
    public int numIslands(char[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){
                    fun_DFS(grid , i , j);
                    n ++;
                }
            }
        }
        return n;

    }
    public void fun_DFS(char[][] grid , int fx , int fy){
        if (grid[fx][fy] == '1'){
            grid[fx][fy] = '2';
            for (int i = 0 ; i < 4 ; i++){
                int nx = fx + x[i];
                int ny = fy + y[i];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == '1'){
                    fun_DFS(grid , nx , ny);
                }
            }
        }
    }
    public void fun_BFS(char[][] grid , int fx , int fy){
        Deque<Point> que = new ArrayDeque<>();
        que.offer(new Point(fx , fy));
        while (!que.isEmpty()){
            Point point = que.poll();
            if (grid[point.x][point.y] == '1'){
                grid[point.x][point.y] = '2';
            }
            for (int i = 0 ; i < 4 ; i ++){
                int nx = point.x + x[i];
                int ny = point.y + y[i];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == '1'){
                    que.offer(new Point(nx , ny));
                }
            }
        }
    }
    //辅助BFS的点类
    public class Point{
        int x;
        int y;

        public Point() {
        }
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
